package LearnDataStructure.a_线性结构.例题;

/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-03 15:23
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.a_线性结构.例题
 */
/*有两个用链表表示的整数，每个结点包含一个数位。
这些数位是反向存放的，也就是个位排在链表的首部。编写函数对这两个整数求和，并用链表形式返回结果。
给定两个链表ListNode* A，ListNode* B，请返回A+B的结果(ListNode*)。
测试样例：
{1,2,3},{3,2,1}
返回：{4,4,4}

{7,4,0,7,5},{2,7,2,3,4}
返回：{9,1,3,0,0,1}
*/
public class e_链表代表数位相加 {
    public static void main(String[] args) {
        e_链表代表数位相加 test = new e_链表代表数位相加();
        int[] arrX = new int[] {3,2,1,5,1};
        int[] arrY = new int[] {1,2,3,9};
        test.usePlus(arrX,arrY);
        System.out.println();
        test.usePlusOther(arrX,arrY);
    }

    public void usePlus(int[] arrX, int[] arrY) {
        CaseNode xHead = new CaseNode(arrX[0]);
        CaseNode px = xHead;
        for (int i = 1; i < arrX.length; i++) {
            px.next = new CaseNode(arrX[i]);
            px = px.next;
        }
        CaseNode yHead = new CaseNode(arrY[0]);
        CaseNode py = yHead;
        for (int i = 1; i < arrY.length; i++) {
            py.next = new CaseNode(arrY[i]);
            py = py.next;
        }
        CaseNode node = plus(xHead, yHead, 0);
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }

    /**
     * 使用递归
     * @param x
     * @param y
     * @param num
     * @return
     */
    public CaseNode plus(CaseNode x, CaseNode y, int num) {
        if (x == null && y == null && num == 0) {
            return null;
        }
        int value = num;
        if (x != null) {
            value += (int)x.data;
        }
        if (y != null) {
            value += (int)y.data;
        }
        CaseNode res = new CaseNode(value % 10);
        res.next = plus(
                x != null ? x.next : null,
                y != null ? y.next : null,
                value >= 10 ? 1 : 0
        );
        return res;
    }

    /**
     * 考虑到a,b可能没对齐，就先对齐
     * @param arrX
     * @param arrY
     */
    public void usePlusOther(int[] arrX, int[] arrY) {
        CaseNode xHead = new CaseNode(arrX[0]);
        CaseNode px = xHead;
        for (int i = 1; i < arrX.length; i++) {
            px.next = new CaseNode(arrX[i]);
            px = px.next;
        }
        CaseNode yHead = new CaseNode(arrY[0]);
        CaseNode py = yHead;
        for (int i = 1; i < arrY.length; i++) {
            py.next = new CaseNode(arrY[i]);
            py = py.next;
        }
        //下面的if是对其
        if (arrX.length > arrY.length) {
            for (int i = 0; i < arrX.length - arrY.length; i++) {
                py.next = new CaseNode(0);
                py = py.next;
            }
        } else if (arrY.length > arrX.length){
            for (int i = 0; i < arrY.length - arrX.length; i++) {
                px.next = new CaseNode(0);
                px = px.next;
            }
        }
        nodeAndValue other = plusOther(xHead, yHead);
        CaseNode node = other.node;
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
    }

    /**
     * 如果正向排列
     * @param a
     * @param b
     * @return nodeAndValue
     */
    public nodeAndValue plusOther(CaseNode a, CaseNode b) {
        if (a.next == null && b.next == null) {
            int value = (int)a.data + (int)b.data;
            return new nodeAndValue(
                    new CaseNode(value),
                    value >= 10
            );
        }
        nodeAndValue other = plusOther(a.next, b.next);
        int value = 0;
        if (other.flag) {
            value = (int)a.data + (int)b.data + 1;
        } else {
            value = (int)a.data + (int)b.data;
        }
        if (value >= 10) {
            CaseNode res = new CaseNode(value % 10);
            res.next = other.node;
            return new nodeAndValue(res,true);
        } else {
            CaseNode res = new CaseNode(value);
            res.next = other.node;
            return new nodeAndValue(res,false);
        }
    }

    public class nodeAndValue {
        public CaseNode node;
        public boolean flag;

        public nodeAndValue(CaseNode node, boolean flag) {
            this.node = node;
            this.flag = flag;
        }

        @Override
        public String toString() {
            return "nodeAndValue{" +
                    "node=" + node +
                    ", flag=" + flag +
                    '}';
        }
    }
}
